#include <bits/stdc++.h>

using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

void printf_list(ListNode *head)
{
    ListNode *cur = head;
    while (cur != nullptr)
    {
        printf("%d ", cur->val);
        cur = cur->next;
    }
    printf("\n");
}

class Solution
{
public:
    // ListNode *removeNthFromEnd(ListNode *head, int n)
    // {
    //     ListNode *dummy_head = new ListNode(0);
    //     dummy_head->next = head;
    //     ListNode *cur = dummy_head;
    //     int count = 0;
    //     while (cur->next != nullptr)
    //     {
    //         count++;
    //         cur = cur->next;
    //     }
    //     int circle_num = count - n;
    //     cur = dummy_head;
    //     while (circle_num != 0)
    //     {
    //         circle_num--;
    //         cur = cur->next;
    //     }
    //     ListNode *tmp = cur->next;
    //     cur->next = cur->next->next;
    //     delete tmp;
    //     tmp = nullptr;
    //     ListNode *res = dummy_head->next;
    //     delete dummy_head;
    //     dummy_head = nullptr;
    //     return res;
    // }

    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        ListNode *dummy_head = new ListNode(0);
        dummy_head->next = head;
        ListNode *fast = dummy_head;
        ListNode *slow = dummy_head;
        while (n != 0)
        {
            n--;
            fast = fast->next;
        }
        fast = fast->next;
        while (fast != nullptr)
        {
            fast = fast->next;
            slow = slow->next;
        }
        ListNode *node = slow->next;
        slow->next = slow->next->next;
        delete node;
        node = nullptr;
        ListNode *res = dummy_head->next;
        delete dummy_head;
        dummy_head = nullptr;
        return res;
    }
};

int main()
{
    ListNode *head = new ListNode(1);
    ListNode *node1 = new ListNode(2);
    ListNode *node2 = new ListNode(3);
    ListNode *node3 = new ListNode(4);
    ListNode *node4 = new ListNode(5);

    head->next = node1;
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;

    printf_list(head);

    Solution sol;
    ListNode *remove_head = sol.removeNthFromEnd(head, 2);

    printf_list(remove_head);

    return 0;
}